package demo5;

/**
 * 递归_Pow(x,n) - 快速幂
 * https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
 */
class Solution2 {
    public double myPow(double x, int n) {
        return n < 0 ? 1/dfs(x,-n) : dfs(x,n);
    }

    private double dfs(double x, int n) {
        // 出口
        if(n == 0) return 1;
        double tmp = dfs(x,n/2);
        return n % 2 == 0 ? tmp * tmp :  tmp * tmp * x;
    }
}